An accurate and efficient algorithm for detection of radio bursts with an unknown dispersion measure, for single dish telescopes and interferometers

摘要

Astronomical radio bursts disperse while traveling through the interstellarmedium. To optimally detect a short-duration signal within a frequency band, wehave to precisely compensate for the pulse dispersion, which is acomputationally demanding task. We present the Fast Dispersion MeasureTransform (FDMT) algorithm for optimal detection of such signals. Our algorithmhas a low theoretical complexity of 2N_f N_t+ N_t N_d log_2(N_f) where N_f, N_tand N_d are the numbers of frequency bins, time bins, and dispersion measurebins, respectively. Unlike previously suggested fast algorithms our algorithmconserves the sensitivity of brute force dedispersion. Our tests indicate thatthis algorithm, running on a standard desktop computer, and implemented in ahigh-level programming language, is already faster than the state of the artdedispersion codes running on graphical processing units (GPUs). We alsopresent a variant of the algorithm that can be efficiently implemented on GPUs.The latter algorithm's computation and data transport requirements are similarto those of two-dimensional FFT, indicating that incoherent dedispersion cannow be considered a non-issue while planning future surveys. We further presenta fast algorithm for sensitive dedispersion of pulses shorter than normallyallowed by incoherent dedispersion. In typical cases this algorithm is ordersof magnitude faster than coherent dedispersion by convolution. We analyze thecomputational complexity of pulsed signal searches by radio interferometers. Weconclude that, using our suggested algorithms, maximally sensitive blindsearches for such pulses is feasible using existing facilities. We provide animplementation of these algorithms in Python and MATLAB.